home *** CD-ROM | disk | FTP | other *** search
/ PC Elektro 3 / PC-Elektro-3-cd1.bin / KBan 2.0 / KBANSRC.LZH / SRC / PROG / NETLIST / SEGSEG.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-23  |  3.7 KB  |  119 lines
  1. // the implementation of segseg
  2. // Copyright (C) 1997 Kazutaka Hirata <khirata@jove.acs.unt.edu>
  3.  
  4. #include "../common/base.h"
  5. #include "hesse.h"
  6. #include "seg.h"
  7. #include "xydbl.h"
  8.  
  9. #include "segseg.h"
  10.  
  11. bool is_parallel(const XY_DBL& v1, const XY_DBL& v2)
  12. {
  13.   return v1.x() * v2.y() == v1.y() * v2.x();
  14. }
  15.  
  16. double segseg_core(const SEGMENT& seg1, const SEGMENT& seg2)
  17. {
  18.   double distance = get_distance(seg1.p1(), seg2.p1());
  19.   distance = minimum(distance, get_distance(seg1.p1(), seg2.p2()));
  20.   distance = minimum(distance, get_distance(seg1.p2(), seg2.p1()));
  21.   distance = minimum(distance, get_distance(seg1.p2(), seg2.p2()));
  22.   HESSE hesse_1_1(SEGMENT(seg1.p1() - seg2.p1(), seg1.p2() - seg2.p1()));
  23.   HESSE hesse_1_2(SEGMENT(seg1.p1() - seg2.p2(), seg1.p2() - seg2.p2()));
  24.   HESSE hesse_2_1(SEGMENT(seg2.p1() - seg1.p1(), seg2.p2() - seg1.p1()));
  25.   HESSE hesse_2_2(SEGMENT(seg2.p1() - seg1.p2(), seg2.p2() - seg1.p2()));
  26.   if(hesse_1_1.on_segment()
  27.   || hesse_1_2.on_segment()
  28.   || hesse_2_1.on_segment()
  29.   || hesse_2_2.on_segment()) {
  30.     if(hesse_1_1.on_segment()) {
  31.       distance = minimum(distance, hesse_1_1.c());
  32.     }
  33.     if(hesse_1_2.on_segment()) {
  34.       distance = minimum(distance, hesse_1_2.c());
  35.     }
  36.     if(hesse_2_1.on_segment()) {
  37.       distance = minimum(distance, hesse_2_1.c());
  38.     }
  39.     if(hesse_2_2.on_segment()) {
  40.       distance = minimum(distance, hesse_2_2.c());
  41.     }
  42.   } else {
  43.   }
  44.   return distance;
  45. }
  46.  
  47. double segseg(const SEGMENT& seg1, const SEGMENT& seg2)
  48. {
  49.   XY_DBL v1 = seg1.get_vector();
  50.   XY_DBL v2 = seg2.get_vector();
  51.  
  52.   double distance;
  53.   if(is_parallel(v1, v2)) {
  54.     SEGMENT seg(seg1.p1(), seg2.p1());
  55.     XY_DBL v = seg.get_vector();
  56.     if(is_parallel(v, v1)) {
  57.       if(seg1.is_vertical()) {
  58.         double y1_max = maximum(seg1.p1().y(), seg1.p2().y());
  59.         double y1_min = minimum(seg1.p1().y(), seg1.p2().y());
  60.         double y2_max = maximum(seg2.p1().y(), seg2.p2().y());
  61.         double y2_min = minimum(seg2.p1().y(), seg2.p2().y());
  62.         if(y1_max < y2_min) {
  63.           distance = y2_min - y1_max;
  64.         } else if (y2_max < y1_min) {
  65.           distance = y2_min - y1_max;
  66.         } else {
  67.           distance = 0;
  68.         }
  69.       } else {
  70.         double x1_max = maximum(seg1.p1().x(), seg1.p2().x());
  71.         double x1_min = minimum(seg1.p1().x(), seg1.p2().x());
  72.         double x2_max = maximum(seg2.p1().x(), seg2.p2().x());
  73.         double x2_min = minimum(seg2.p1().x(), seg2.p2().x());
  74.         if(x1_max < x2_min) {
  75.           double xdst = x2_min - x1_max;
  76.           double ydst = xdst * v1.y() / v1.x();
  77.           distance = sqrt(xdst * xdst + ydst * ydst);
  78.         } else if (x2_max < x1_min) {
  79.           double xdst = x2_min - x1_max;
  80.           double ydst = xdst * v1.y() / v1.x();
  81.           distance = sqrt(xdst * xdst + ydst * ydst);
  82.         } else {
  83.           distance = 0;
  84.         }
  85.       }
  86.     } else {
  87.       distance = segseg_core(seg1, seg2);
  88.     }
  89.   } else {
  90.     double den = v1.y() * (seg2.p1().x() - seg1.p1().x())
  91.                - v1.x() * (seg2.p1().y() - seg1.p1().y());
  92.     double num = v1.x() * v2.y() - v1.y() * v2.x();
  93.     double s = den / num;
  94.     XY_DBL isec(
  95.       v2.x() * s + seg2.p1().x(),
  96.       v2.y() * s + seg2.p1().y()
  97.     );
  98.     bool on_segment1;
  99.     if(seg1.is_vertical()) {
  100.       on_segment1 = seg1.is_y_on_segment(isec.y());
  101.     } else {
  102.       on_segment1 = seg1.is_x_on_segment(isec.x());
  103.     }
  104.     bool on_segment2;
  105.     if(seg2.is_vertical()) {
  106.       on_segment2 = seg2.is_y_on_segment(isec.y());
  107.     } else {
  108.       on_segment2 = seg2.is_x_on_segment(isec.x());
  109.     }
  110.     if(on_segment1 && on_segment2) {
  111.       distance = 0;
  112.     } else {
  113.       distance = segseg_core(seg1, seg2);
  114.     }
  115.   }
  116.  
  117.   return distance;
  118. }
  119.